P3911 最小公倍数之和 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 817字数 简单问题复杂化是解决问题的一个好方法。 令 cic_ici 表示 iii 出现的次数,nnn 为最大数字。 ∑i=1n∑j=1nci×cj×lcm(i,j)\sum_{i=1}^n \sum_{j=1}^nc_i \times c_j \times lcm(i,j) 阅读全文 »
P6156 简单题 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 6分钟 | 983字数 ∑i=1n∑j=1n(i+j)kf(gcd(i,j))gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j) i=1∑nj=1∑n(i+j)kf(gcd(i,j))gcd(i,j) 显然 f(i)=μ2(i)f(i)=\mu^2(i)f(i)=μ2(i) 阅读全文 »
P4619 [SDOI2018]旧试题 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 9分钟 | 1353字数 ∑i=1A∑j=1B∑k=1Cd(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk) i=1∑Aj=1∑Bk=1∑Cd(ijk) ∑i=1A∑j=1B∑k=1C∑x∣i∑y∣j∑z∣k[(x,y)=1][(y,z)=1][(x,z)=1]\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{x|i}\sum_{y|j}\sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1] 阅读全文 »
P4464 [国家集训队]JZPKIL 发布于 2020-09-12 | 分类于 莫比乌斯反演 、 伯努利数 | 11分钟 | 1781字数 如果不知道伯努利数的点这里。 ∑i=1n(i,n)x[i,n]y\sum_{i=1}^n (i,n)^x[i,n]^y i=1∑n(i,n)x[i,n]y 阅读全文 »
P1587 [NOI2016]循环之美 发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 764字数 类比十进制下的纯循环小数,kkk 进制下的纯循环小数满足最简分数分母与 kkk 互质。 而题目要求相同数值只计数一次,所以只需要考虑最简分数的情况。 那么答案为: 阅读全文 »
P2480 [SDOI2010]古代猪文 发布于 2020-09-12 | 分类于 数论 | 4分钟 | 515字数 g∑d∣nCnn/dmod 999911659g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659 g∑d∣nCnn/dmod999911659 g∑d∣nCndmod 999911659g^{\sum_{d|n}C_{n}^{d}} \mod 999911659 阅读全文 »
P5769 [JSOI2016]飞机调度 发布于 2020-09-12 | 分类于 网络流 | 5分钟 | 758字数 网络流24题 为了使飞机数量尽量少,一架飞机尽量多飞几趟航班。 将航班看成一个点,其实就是求最小路径覆盖。 阅读全文 »
P2303 [SDOI2012] Longge 的问题 发布于 2020-09-12 | 分类于 数论 、 欧拉函数 | 2分钟 | 266字数 ∑i=1n(i,n)\sum_{i=1}^n(i,n) i=1∑n(i,n) ∑d∣nd∑i=1n[(i,n)=d]\sum_{d|n}d\sum_{i=1}^n[(i,n)=d] 阅读全文 »
P5130 纯粹的弹幕地狱 发布于 2020-09-12 | 分类于 数论 、 莫比乌斯反演 | 6分钟 | 1028字数 因为每回合击中的概率是固定的,所以只需要算一次。 概率为:可以击中的情况/总情况。 每个点有 (n+1)2(n+1)^2(n+1)2 个位置,所以总情况为(n+1)4(n+1)^4(n+1)4 阅读全文 »
P5451 [THUPC2018]密码学第三次小作业 发布于 2020-09-12 | 分类于 数论 | 3分钟 | 417字数 如果你做过 P4358 [CQOI2016]密钥破解 ,那么你基本上就凉了。 这道题跟背景没有任何关系。 注意到二元不定方程: xe1+ye2=(e1,e2)=1xe1+ye2=(e1,e2)=1xe1+ye2=(e1,e2)=1 阅读全文 »